洛谷题解 CF1716A 【2-3 Moves】

发表于 | 阅读次数：
本文字数： 1.3k | 阅读时长 ≈ 1 分钟

题意翻译

现在有一条坐标轴，你现在坐标为 $0$ ，你每步可以走 $+3,+2,-3,-2$ 个单位问最少经过几步可以到达坐标为 $n$ 的点

解题过程

好吧，这其实是找规律题（毕竟是A题嘛）

首先就先列举出前几个坐标的情况

$n=1$ 时，最少步数为 $2 \ (+3-2)$

$n=2$ 时，最少步数为 $1 \ (+2)$

$n=3$ 时，最少步数为 $1 \ (+3)$

$n=4$ 时，最少步数为 $2 \ (+2+2)$

$n=5$ 时，最少步数为 $2 \ (+2+3)$

$n=6$ 时，最少步数为 $2 \ (+3+3)$

$n=7$ 时，最少步数为 $3 \ (+2+2+3)$

$n=8$ 时，最少步数为 $3 \ (+2+3+3)$

$n=9$ 时，最少步数为 $3 \ (+3+3+3)$

$……$

观察上面的情况，不难发现 $n$ 每增加三个单位最少步数 $+1$（除了在 ${1,2,3}$ 这一段里 $n=1$ 时最少步数为 $1$ ）

其实如果不放心的话还可以再往下列举 （比赛时我列到了15）

用式子表示大概就是 $\operatorname{ans} = \begin{cases} 2 \ (n=1) \\ n/3 \ (n \bmod \ 3 =0)\\ n/3+1 \ (n \bmod \ 3\neq 0)\end{cases} $

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<iostream>
#include<cstdio>
using namespace std;

int n,t,ans=0;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        if(n==1)
        {
            printf("2\n");
        }
        else
        {
            if(n%3!=0)
            {
                ans=n/3+1;
            }
            else
            {
                ans=n/3;
            }
            printf("%d\n",ans);
        }
        
    }
    scanf("%d",&n);
    return 0;
}

题目详见:https://www.luogu.com.cn/problem/show?pid=CF716A